Modern video products and services, such as video capable mobile telecommunications devices, high-definition television broadcasts, internet video, and video recorders, rely on digital video compression. Digital video compression technologies enable transmission and storage of video data by reducing data volume while maintaining various attributes essential to high quality video display.
Digital video compression techniques encompass a variety of methods for reducing the volume of data that must be delivered to reproduce a video display. Removal of redundant information from the video stream reduces the volume of data that must be stored or transmitted without resulting degradation of the reconstructed video. Largely imperceptible information may be removed from the video signal with little or no noticeable loss of quality.
Entropy coding is one technique for removing redundant information from a digital video signal. The coding process endeavors to represent a video signal with as few bits as possible while retaining the information necessary to exactly reconstruct the source video signal. Entropy coding involves elimination of redundant information and representation of necessary information by symbols of the smallest possible average length. Theoretically, the smallest achievable average symbol length that retains all the information necessary to perfectly reconstruct the signal is equivalent to the entropy of the signal. Huffman coding and arithmetic coding are examples of two entropy coding techniques.
Content Adaptive Variable Length Coding (“CAVLC”), as disclosed in ITU-T H.264 which is hereby incorporated by reference, is an entropy coding technique employed in modern digital video encoders. The CAVLC algorithm takes advantage of the fact that power in a quantized transformed pixel block tends to be concentrated in the lower frequencies. CAVLC adapts by selecting a variable length code (“VLC”) table, for coding non-zero coefficients (“levels”) based on the magnitude of recently coded levels. The algorithm's reliance on previously encoded levels tends to give the algorithm a sequential character. Similarly, the number of zero coefficients in each run, where a run is a contiguous string between two levels (“run before”), is encoded based on the number of zero coefficients remaining to be coded in the block. CAVLC also exploits the fact that sequences of ones dominate the levels at the tail of a zigzag reordered quantized coefficient block. CAVLC specially encodes up to three trailing one coefficients (“T1”), thus not all non-zero coefficients are encoded in the same manner.
Such aspects of CAVLC result in high coding efficiency, but also introduce substantial complexity to the coding process. Modern processors rely on extensive pipelining and multiple execution units to achieve high levels of performance. The sequential nature of encoding level and run before limit the opportunities for parallelization of the algorithm, thus limiting performance on processor architectures implementing parallel execution units, such as very long instruction word architectures. The numerous control transfers resulting from conditionals in the CAVLC algorithm cause pipeline breaks that further impair performance on modern processors.